//
// Created by Administrator on 2021/11/16.
// May Saint Diana bless you!
//
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int reductionOperations(vector<int> &nums) {
        // 排序，计算有几个阶梯，每次+高一层阶梯的数量
        sort(nums.begin(), nums.end());
        int n = (int) nums.size();
        int ans = 0;
        int pos = n - 1;
        while (pos > 0) {
            while (pos > 0 and nums[pos] == nums[pos - 1]) {
                --pos;
            }
            // 走到下一层阶梯
            --pos;
            if (pos >= 0) {
                ans += n - 1 - pos;
            }
        }
        return ans;
    }
};

class Solution2 {
public:
    /**
     * 首先，为了使得 nums 中所有元素相等，我们需要将nums 中的任意元素都变为 nums 中的最小值。
    其次，考虑 nums 中的任意元素 x，每次操作（如有）只能将它变成严格小于它的元素中的最大值。
     为了将 x 变为nums 中的最小值，需要的操作次数即为严格小于它的不同值的数量。
     * @param nums
     * @return
     */
    int reductionOperations(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int res = 0;   // 总操作次数
        int cnt = 0;   // 每个元素操作次数
        for (int i = 1; i < n; ++i) {
            if (nums[i] != nums[i - 1]) {
                ++cnt;
            }
            res += cnt;
        }
        return res;
    }
};

int main() {
    vector<int> nums{3, 1, 5};
    Solution solution;
    cout << solution.reductionOperations(nums) << endl;
    return 0;
}


